/**
 * 单向链表
 * 1、主要包含两个对象一个节点对象（节点对象包含两个属性一个是值另一个是节点元素的下一个下标）、一个链表对象
 * 2、反转：实现了两种的反转方法 a、递归的方法 b、遍历生成
 */
//节点对象
class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}
//链表对象
class LinkedList {
  constructor() {
    this.head = null; //链表的头对象
    this.size = 0; //记录链表的长度 从0开始记录
  }
  //添加节点
  add(index, element) {
    //有传index和没有传index
    if (arguments.length == 1) {
      element = index;
      index = this.size;
    }
    //考虑越界即小于0的问题
    if (index < 0 || index > this.size) {
      throw new Error("小于0或者下标不能大于链表的长度");
    }
    if (index == 0) {
      this.head = new Node(element, this.head);
    } else {
      //在链条的某个节点前后插入一个节点
      let frontNode = this.getNode(index - 1);
      let newNode = new Node(element, frontNode.next);
      frontNode.next = newNode;
    }
    this.size++;
  }
  //获取节点
  getNode(index) {
    let current = this.head;
    while (index) {
      index--;
      current = current.next;
    }
    return current;
  }
  //删除节点 判断是否删除的是0下标
  remove(index) {
    let removeNode;
    if (index == 0) {
      let head = this.head;
      if (!!head || !!head.next) {
        removeNode = null;
      } else {
        removeNode = head.next;
      }
    } else {
      let frontNode = this.getNode(index - 1);
      removeNode = frontNode.next = frontNode.next.next;
    }
    this.size--;
    return removeNode && removeNode.element;
  }
  //链表的长度
  len() {
    return this.size;
  }
  //递归反转，递归位置没有发生改变，只是指针的指向发生了改变
  reverseLinked1() {
    function reverse(head) {
      if (!head || !head.next) return head;
      let newHead = reverse(head.next);
      head.next.next = head;
      head.next = null;
      return newHead;
    }
    this.head = reverse(this.head);
    return this.head;
  }
  //使用循环进行反转
  reverseLinked2() {
    let head = this.head,
      newHead = null,
      tempNode = null;
    while (!!head) {
      tempNode = head.next; //暂存下一个链表的指针
      head.next = newHead; //将久头的指向新的头节点，新旧头关联上
      newHead = head; //新头等于久头
      head = tempNode; //久头指向久的后面节点
    }
    this.head = newHead;
    return this.head;
  }
}

let ll = new LinkedList();
ll.add(0, 300);
ll.add(0, 200);
ll.add(0, 100);
console.dir(ll, { depth: 10 });
// console.dir(ll.reverseLinked1(), { depth: 10 });
console.dir(ll.reverseLinked2(), { depth: 10 });
// ll.add(300);
// ll.add(400);
// ll.add(500);
// console.dir(ll, { depth: 10 }); //100 200 300 400
// ll.remove(2);
// console.dir(ll, { depth: 10 }); //100 200 300 400
